#include "csbmath.h"
#include "convex_polygon.h"

#ifdef __cplusplus
extern "C" {
#endif

// 是否使用投影的方式来计算多边形和多边形的碰撞
// NOTE:在对称的边数较多的多边形里使用这种方式也许会较好
// 一般的碰撞循环判定点在多边形内将更快
//#define POLYGON_LOVE_POLYGON_USE_PROJECTION	1

// 组成多边形的最少点数
#define MIN_CP_POINT_NUM	3	

/*********************| static data |*********************/
#ifdef POLYGON_LOVE_POLYGON_USE_PROJECTION
/* 获得_n_多边形顶点索引为_idx_的下一个顶点索引 */
#define CP_NEXT_VETEX_IDX(_idx_, _n_)	(((_idx_) == (_n_ - 1)) ? 0 : (_idx_ + 1))

struct ratearr_t{
	uint32_t	num;
	float*		rates;
};

struct drop_t {
	const convex_polygon_t* pcpA;
	const convex_polygon_t* pcpB;
	float a;
	float amin;
	float amax;
	float bmin;
	float bmax;
};

/*********************| static functions |*********************/
/* 获得两点组成的直线的斜率 */
static float pp_rate(pos_t* a, pos_t* b)
{
	float t = b->x - a->x;
	if (t > -1 && t < 1) {
		return 0;
	}
	return (b->y - a->y) / t;
}


/* 如果rate不存在于parr->rates那么添加到parr->rates尾巴上 */
static bool try_add_rate(struct ratearr_t* parr,const float rate)
{
	uint32_t i = 0;
	for (i = 0; i< parr->num; ++i) {
		if (rate == parr->rates[i])
			return false;
	}
	parr->rates[i] = rate;
	++parr->num;
	return true;
}

/* 获取多边形在y = a * x直线上的投影 */
static void drop_yax(struct drop_t* pdrop)
{
	// 投影计算，顶点坐标(n, m),x = (n + a*m) / (a * a + 1), y = a * x
	uint32_t i = 1;
	float a2 = pdrop->a * pdrop->a;

	float tmp = (pdrop->pcpA->points[0].x + pdrop->a * pdrop->pcpA->points[0].y) / (a2  + 1);
	pdrop->amin = pdrop->amax = tmp;
	while(i < pdrop->pcpA->pnum) {
		// min max judge
		tmp = (pdrop->pcpA->points[i].x + pdrop->a * pdrop->pcpA->points[i].y) / (a2 + 1);
		if (tmp < pdrop->amin)
			pdrop->amin = tmp;
		else if (tmp > pdrop->amax) {
			pdrop->amax = tmp;
		}
		++i;
	}

	i = 1;
	tmp = (pdrop->pcpB->points[0].x + pdrop->a * pdrop->pcpB->points[0].y) / (a2  + 1);
	pdrop->bmin = pdrop->bmax = tmp;
	while(i < pdrop->pcpB->pnum) {
		// min max judge
		tmp = (pdrop->pcpB->points[i].x + pdrop->a * pdrop->pcpB->points[i].y) / (a2 + 1);
		if (tmp < pdrop->bmin)
			pdrop->bmin = tmp;
		else if (tmp > pdrop->bmax) {
			pdrop->bmax = tmp;
		}
		++i;
	}
}

static void drop_y(struct drop_t* pdrop)
{
	// 投影计算，顶点坐标(n, m) x = 0, y = m
	uint32_t i = 1;
	int32_t tmp = 0;
	pdrop->amin = pdrop->amax = pdrop->pcpA->points[0].y;
	while(i < pdrop->pcpA->pnum) {
		// min max judge
		tmp = pdrop->pcpA->points[i].y;
		if (tmp < pdrop->amin) {
			pdrop->amin = tmp;
		} else if (tmp > pdrop->amax) {
			pdrop->amax = tmp;
		}
		++i;
	}

	pdrop->bmin = pdrop->bmax = pdrop->pcpB->points[0].y;
	i = 1;
	while(i < pdrop->pcpB->pnum) {
		// min max judge
		tmp = pdrop->pcpB->points[i].y;
		if (tmp < pdrop->bmin) {
			pdrop->bmin = tmp;
		} else if (tmp > pdrop->bmax) {
			pdrop->bmax = tmp;
		}
		++i;
	}
}

static void drop_x(struct drop_t* pdrop)
{
	// 投影计算，顶点坐标(n, m),x = n, y = 0
	uint32_t i = 1;
	int32_t tmp = 0;
	pdrop->amin = pdrop->amax = pdrop->pcpA->points[0].x;
	while(i < pdrop->pcpA->pnum) {
		// min max judge
		tmp = pdrop->pcpA->points[i].x;
		if (tmp < pdrop->amin) {
			pdrop->amin = tmp;
		} else if (tmp > pdrop->amax) {
			pdrop->amax = tmp;
		}
		++i;
	}

	pdrop->bmin = pdrop->bmax = pdrop->pcpB->points[0].x;
	i = 1;
	while(i < pdrop->pcpB->pnum) {
		// min max judge
		tmp = pdrop->pcpB->points[i].x;
		if (tmp < pdrop->bmin) {
			pdrop->bmin = tmp;
		} else if (tmp > pdrop->bmax) {
			pdrop->bmax = tmp;
		}
		++i;
	}
}
#endif
/*********************| 外部接口 |*********************/
/* 使用点线斜率差判定是否在多边形内 */
bool point_in_CP(const pos_t* ppos, const convex_polygon_t* pcp)
{
	csberrno = CSBERR_NOERR;
	CSB_NO_ERR_RET(ppos && pcp && pcp->points && pcp->pnum >= MIN_CP_POINT_NUM,
		   CSBERR_PARAM, false);
	uint32_t i , j;
	uint32_t c1 = 0, c2 = 0;
	int32_t tmp;
	for (i = 0, j = pcp->pnum - 1; i< pcp->pnum; j = i++) {
		tmp = (ppos->x - pcp->points[j].x) * (pcp->points[i].y - pcp->points[j].y) -
		      (ppos->y - pcp->points[j].y) * (pcp->points[i].x - pcp->points[j].x);
		if (tmp > 0)
			++c1;
		else if (tmp < 0)
			++c2;
	}
	return !c1 || !c2;
}

bool CP_love_CP(const convex_polygon_t* pcpA, const convex_polygon_t* pcpB)
{
	csberrno = CSBERR_NOERR;
	CSB_NO_ERR_RET(pcpA && pcpB && pcpA->points && pcpB->points &&
		   pcpA->pnum >= MIN_CP_POINT_NUM && pcpB->pnum >= MIN_CP_POINT_NUM,
		   CSBERR_PARAM, false);
#ifdef POLYGON_LOVE_POLYGON_USE_PROJECTION
	// 用投影检测
	bool bret = true;
	struct ratearr_t ratearr = {0, NULL}; // 两个多边形的边的已经计算过的斜率数组
	uint32_t nside = pcpA->pnum + pcpB->pnum;
	float tmp[CP_POINT_LIMIT + CP_POINT_LIMIT];
	memset(tmp, 0, sizeof(tmp));
	if (nside > (CP_POINT_LIMIT + CP_POINT_LIMIT)) {
		do {
			ratearr.rates = (float*)malloc(sizeof(float)*nside);
		} while (!ratearr.rates);
	} else {
		ratearr.rates = tmp;
	}
	uint32_t i = 0, inext = 0, inow = 0;
	const convex_polygon_t* pcpnow = pcpA;
	struct drop_t drop = {pcpA, pcpB, 0};
	bool ye0 = true, xe0 = true;
	bool dosome = false;
	while (i < nside) {
		dosome = false;
		if (i >= pcpA->pnum) {
			pcpnow = pcpB;
			inow = i - pcpA->pnum;
		} else {
			inow = i;
		}
		inext = CP_NEXT_VETEX_IDX(inow, pcpnow->pnum);
		drop.a = pp_rate(&pcpnow->points[inow], &pcpnow->points[inext]);
		if (drop.a) {
			// 计算每个边的斜率a，查询是否已经计算过,没有的话就插入到rates里面
			if (try_add_rate(&ratearr, drop.a)) {
				// 计算两个多边形做法线的投影x
				drop.a = -1 / drop.a;
				drop_yax(&drop);
				dosome = true;
			}
		} else {
			if (pcpnow->points[inow].x == pcpnow->points[inext].x) {
				// x = 0 line, alex drop on y
				if (xe0) {
					drop_y(&drop);
					xe0 = false;
					dosome = true;
				}
			} else {
				// y = 0 line, alex drop on  x
				if (ye0) {
					drop_x(&drop);
					ye0 = false;
					dosome = true;
				}
			}
		}
		if (dosome && ((drop.amax < drop.bmin) || drop.amin > drop.bmax)) {
			bret = false;
			break;
		}
		++i;
	}
	// release rates point memory
	if (nside > (CP_POINT_LIMIT + CP_POINT_LIMIT))
		free(ratearr.rates);
	return bret;
#else
	uint32_t i = pcpA->pnum;
	while (i --> 0) {
		if (point_in_CP(&pcpA->points[i], pcpB)) {
			return true;
		}
	}
	i = pcpB->pnum;
	while (i --> 0) {
		if (point_in_CP(&pcpB->points[i], pcpA)) {
			return true;
		}
	}
	return false;
#endif
}


void CP_copy(const convex_polygon_t* src, convex_polygon_t* dest)
{
	csberrno = CSBERR_NOERR;
	CSB_NO_ERR_VRET(src && dest && src->points && dest->points &&
		   src->pnum >= MIN_CP_POINT_NUM, CSBERR_PARAM);
	dest->pnum = 0;
	while (dest->pnum < src->pnum) {
		dest->points[dest->pnum] = src->points[dest->pnum];
		++dest->pnum;
	}
}

void CP_elebase_coll(const elebase_t* pele, const convex_polygon_t* oriCP, convex_polygon_t* out)
{
	csberrno = CSBERR_NOERR;
	CSB_NO_ERR_VRET(pele && oriCP && out && out->points && oriCP->points, CSBERR_PARAM);
	// rotate, scale , move
	float tmpx=0, tmpy = 0;
	uint32_t i = 0;
	while (i < oriCP->pnum) {
		tmpx = oriCP->points[i].x * pele->scale.xs;
		tmpy = oriCP->points[i].y * pele->scale.ys;
		CSB_rotate(&tmpx, &tmpy, pele->rotate);
		out->points[i].x = tmpx + pele->pos.x;
		out->points[i].y = -tmpy + pele->pos.y;
		++i;
	}
	out->pnum = oriCP->pnum;
}

#ifdef __cplusplus
} /* end extern C */
#endif
